1. Field of the Invention
The present invention relates to a method for scheduling the emission of asynchronous transfer mode (ATM) cells from an ATM cell queuing device. More particularly, the present invention relates to a system for controlling the emission of ATM cells while maintaining a desired quality of service (QoS) for different signal traffic provided to a telephone service subscriber.
2. Background
The following description is intended to provide a context for a description of the invention, and is not intended to constitute an admission of prior art.
The telecommunications industry has developed schemes for transmitting telephone signals in digital formats. In one format, termed time division multiplexing (TDM), plain old telephone (POTs) voice signals are provided in a digital format for transmission. In another format, the ATM format, broadband digital signals which are provided from computers or fax machines are configured for transmission. Separate transmission paths are typically provided for the ATM and TDM signals. In the future it is desirable to provide all signals in an ATM format to avoid the need for separate transmission paths and separate transmission equipment.
An ATM signal from a telephone service subscriber is divided into cells or packets, and cells from multiple sources and multiple destinations are asynchronously multiplexed together during transmission. ATM cells are multiplexed when transmitted from node to node in a network. In each node a network switch or queuing device selects both the order of transmission for cells and the next node to where the cell is retransmitted. It is desirable that network switches be capable of supporting network traffic of various characteristics including both Constant Bit Rate (CBR) traffic, with a fixed time guarantee for delivery, and Unassigned Bit Rate (UBR) traffic.
CBR traffic is needed to assure that POTs voice signals are transmitted without delays so that voice signals are not interrupted, and so that no delay is apparent to listeners receiving the signals. UBR traffic can experience delays, and is typically delivered in time frames based on an assigned Quality of Service (QoS). The QoS, for instance, can be based upon a rate a subscriber pays.
The structure of a typical ATM cell is depicted in FIG. 1. Each ATM cell is typically 53 bytes long, with 5 bytes reserved for a packet header to identify routing and other information for the cell payload data being transferred, and 48 bytes reserved for storing the ATM payload data. The generic flow control (GFC) of the header is used for identifying a user network interface (UNI) and can include bits for cell flow control. The Virtual Path Identifier (VPI) and Virtual Circuit Identifier (VCI) fields identify every circuit or node along a path which the cell is to be transferred. The Payload Type (PT) identifies the payload data as user data, OAM data, or resource management data. The Cell Loss Priority (CLP) indicates a priority for the cell used in scheduling transmission of the cell through a network. Header Error Check (HEC) bits are included for use in determining if transmission errors have occurred when the ATM cell is transferred. The Payload Bytes store the ATM cell data.
The header information of the ATM cell identifies a routing connection for the cell between two stations, also referred to as a Virtual Circuit (VC). To establish the VC, a first end station requests a connection to a second end station by submitting a connection request to a User to Network Interface (UNI) with the network. After the VC is established, the end stations exchange ATM cells with header information identifying the VC routing.
With ATM cells arriving at a node faster than the ATM switch can transmit other ATM cells out, the ATM switch must schedule the transmission of each cell. The cells are in general buffered at each switch in queues to accommodate congestion. Assuming no congestion, cells which are received from an incoming link at a switch are immediately transmitted over an outgoing link to another destination. When congestion occurs, cells are typically assigned a priority and stored in a first in first out (FIFO) queue by the priority. The queued cells are then transmitted in an order dictated by priority.
A desirable function of a switch or queuing device in an ATM network is to support the QoS for each VC to which the station is connected. The QoS identifies peak and average data rates for a service a user is assigned. To assure a constant bit rate is met for CBR traffic, the CBR traffic can be assigned to the highest QoS, while a user with an Unassigned Bit Rate (UBR) will have a rate controlled to be less than a peak value depending on its QoS parameter. The QoS parameters include Peak Cell Rate (PCR), Cell Delay Variation (CDV) Tolerance, and Sustainable Cell Rate (SCR). The PCR defines an upper bound on the cell rate of a VC connection. The SCR is an upper bound on the average cell transmission rate over the connection. For Constant Bit Rate (CBR) connections, usually attributed to premium rate services, no SCR is defined. The CDV tolerance parameter indicates the degree of distortion allowed in the interarrival time of cells on a requested connection.
An end node as well as an intermediate node for a VC may police traffic to ensure that a VC does not exceed the PCR or SCR for the QoS assigned to an ATM cell. If a node detects transmission rates in excess of the QoS for a VC, it can typically police traffic by discarding an ATM cell.
FIG. 2 shows components of an access network channel bank 10 used to distribute ATM signals to and from subscribers. The channel bank shown includes subscriber slots 12 for attachment of subscriber line cards 14. The line cards 14 provide signals to and from subscribers and can function to generate ATM signals from POT connections, such as from line 16, and further create ATM cells from signals generated from components such as personal computers on lines, such as line 18. Signals are provided on an interface bus 20 on a backplane to and from the line cards 14. The cell bus 20 is further connected to a channel bank control unit 22.
The channel bank structure also includes a transport slot 24 for connection of a transport card 26. The transport slot 24 is connected by a interface cell bus 29 to the bank control unit. The transport card 26 includes a cell bus interface buffer 28 for connecting to the cell bus 28, a multiplexer/demultiplexer 30 for connecting the cell bus interface buffer 28 to a buffer 32, and the buffer 32 further connects to multiple lines which are provided to an internet service provider (ISP).
The multiplexer/demultiplexer may be controlled by an ATM LAyer Solution (ATLAS) 34. Such an ATLAS chip is manufactured by PMC Sierra, Inc. The ATLAS 34 provides ATM header lookup to determine cell routing and also functions to police ATM traffic QoS parameters for a VC using a double leaky bucket method. The double leaky bucket system determines whether a VC assigned to the ATM cell exceeded the QoS parameters for the cell. To perform policing for the QoS parameters, the ATLAS 34 either drops the ATM cell or provides a note or tag with the cell header identifying the violation. ATLAS hardware to enable such policing is significant and includes counters, timers and control logic for each potential VC connection to a network station.
The channel bank control unit 22 includes components for routing ATM cells between the subscriber line cards and the transport card 24. The channel bank control unit 22 includes components such as Field Programmable Gate Arrays (FPGAs) along with buffer memories used for routing ATM cells.
It is desirable to provide circuitry in a channel bank control unit to control the transmission of ATM cells according to their QoS parameters so that QoS parameters are not exceeded and ATM cells are not dropped by a policing function, such as the policing carried out by ATLAS 34, in an end node. It is further desirable to provide circuitry in the channel bank control unit to control distribution of ATM cells to devices according to bandwidth allocated to the device. For instance, if the telephone on line 16 operates at a rate of less than 1 MHZ, while the computer on line 18 operates at a rate of more than 50 MHZ, it would be desirable to distribute ATM cells on line 18 at the 50 MHZ rate while holding the cells for line 16, if QoS parameter limits are not violated, rather than providing all of the cells on line 16 first while holding the cells on line 18.
In accordance with the present invention, a Weighted Round Robin (WRR) engine is provided in a scheduler system of a channel bank control unit with components which operate to control the transmission of ATM cells according to their QoS parameters. The WRR in accordance with the present invention can further distribute ATM cells to different subscriber devices according to bandwidth allocated to those devices.
The scheduler system in accordance with the present invention includes a number of port shapers. A port shaper can support a number of flows. A port shaper directs flows to a single subscriber. Each flow assigned to a port shaper identifies ATM cells which are to be distributed to each subscriber device, such as a telephone or computer.
The port shaper includes a number of time descriptors. Flows are linked to the time descriptors. The time descriptors are sequentially activated. When a time descriptor becomes active, a flow linked to the time descriptor can emit an ATM cell, and after emitting the cell the flow is relinked to subsequent time descriptors.
Multiple flows may be linked to the same time descriptor. Since only one flow can emit an ATM cell at a time, arbitration can be performed to determine which flow emits a cell. Such arbitration is performed by a WRR engine. A WRR engine in accordance with the present invention functions using QoS parameters and/or weighting to determine which flow linked to the time descriptor gets to emit a cell.
In one type of WRR engine, termed an Inter-QoS WRR, flows are linked to the time descriptors of the port shapers through their QoS parameters. A tag value is further assigned to each QoS parameter. The tag value is initially set based on a weight assigned to the QoS, and whenever the QoS is selected by the Inter-QoS WRR to have a flow emit an ATM cell, the tag value for the QoS is incremented by its weight.
When an arbitration request is placed to the Inter-QoS WRR, the QoS selected by the WRR is the one with the lowest tag value. If two or more QoSs are tied for the lowest tag value, the higher numbered QoS is selected by the WRR engine. Using the Inter-QoS WRR, a flow directed to a 50 MHZ device may be assigned a high weight while a flow directed to a 1 MHZ device may be assigned a low weight so that flows are more frequently selected for emitting ATM cells toward the 1 MHZ device. Further, bandwidth is also allocated by assigning higher QoS values to flows needing more bandwidth.
In another type of WRR engine, termed an Inter-Flow WRR, flows are linked to time descriptors of port shapers based on a tag-value assigned to the flow with a lowest tag value linked first. The flow linked first is chosen by the Inter-flow WRR to emit an ATM cell. The Inter-Flow WRR enables control of bandwidth for flows which are linked to the same QoS. The tag value for a flow is initially set based on a rate limiting increment (I) assigned to the flow and the tag is incremented by the increment (I) for the flow each time the Inter-Flow WRR selects the flow for emitting a cell. By setting the increment (I) for a flow, the frequency the flow emits ATM cells can be controlled relative to other flows, enabling control of bandwidth using the Inter-Flow WRR engine.